﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _02_LinkedList
{
   class RandList
   {
      public RandList rand { get; set; }

      public RandList next { get; set; }

      public int val { get; set; }

      public RandList(int val)
      {
         this.val = val;
         rand = null;
         next = null;
      }

      // 复制随机链表
      public RandList CopyLinkedList()
      {
         // 构建<原结点，拷贝结点>映射
         Dictionary<RandList, RandList> dic = new Dictionary<RandList, RandList>();
         for (RandList p = this; p != null; p = p.next)
         {
            dic.Add(p, new RandList(p.val));
         }

         // 构建next和rand指向
         for (RandList p = this; p != null; p = p.next)
         {
            if (p.next != null)
               dic[p].next = dic[p.next];
            if (p.rand != null)
               dic[p].rand = dic[p.rand];
         }

         return dic[this];
      }
   }
}
